Aller au contenu principal

Tri par tas (Heap Sort)

Idée centrale​

À chaque tour : trouver le plus grand élément, le placer à la fin, ne plus jamais le toucher, recommencer sur ce qui reste.

[4, 10, 3, 5, 1]  →  trouve le plus grand (10)  →  le place à la fin
[4,  1, 3, 5, | 10]  →  trouve le plus grand (5)   →  le place à la fin
[4,  1, 3, | 5, 10]  →  ...

La barre | représente la frontière entre la zone encore à trier (gauche) et la zone définitivement triée (droite). À chaque tour, la frontière avance d'un cran vers la gauche — les éléments à droite ne sont plus jamais touchés.

Le problème : comment trouver le plus grand rapidement ?​

Chercher le plus grand en parcourant tout le tableau à chaque tour coûte O(n) × n tours = O(n²) — trop lent.

La solution : maintenir une structure qui garantit que arr[0] est toujours le plus grand. C'est le rôle du tas (max-heap).

C'est quoi un tas (max-heap) ?​

Un tas c'est le tableau ordinaire, mais organisé selon une règle simple :

Chaque élément est plus grand que ses deux "enfants".

On visualise ça comme un arbre :

         10          ← arr[0]  (toujours le plus grand)
       /    \
      5      3       ← arr[1], arr[2]
    /   \
   4     1           ← arr[3], arr[4]

En mémoire c'est juste [10, 5, 3, 4, 1] — la position dans le tableau détermine qui est parent et qui est enfant :

Parent de i    →  (i - 1) / 2
Enfant gauche  →  2 * i + 1
Enfant droit   →  2 * i + 2

Les deux phases​

Phase 1 — Construire le tas​

On réorganise le tableau pour que la règle du tas soit respectée partout. À la fin, arr[0] est le plus grand élément.

On ne traite que la première moitié du tableau (n/2 - 1 jusqu'à 0). Pourquoi ? La deuxième moitié sont des feuilles — des éléments sans enfants. Un élément seul respecte déjà la règle du tas automatiquement, inutile de les vérifier.

         4          ← a des enfants → à vérifier
       /   \
     10     3       ← 10 a des enfants → à vérifier
    /  \
   5    1           ← pas d'enfants → déjà valides, on les ignore

Phase 2 — Trier par extractions successives​

On répète jusqu'à ce que tout soit trié :

  1. Échange arr[0] (le plus grand) avec le dernier élément non trié.
  2. Cet élément est maintenant à sa position finale → frontière avance, on ne le touche plus jamais.
  3. On répare le tas (heapify) pour que le nouveau plus grand remonte en arr[0].

La fonction heapify​

Après un échange, arr[0] n'est plus nécessairement le plus grand. heapify le fait descendre jusqu'à ce qu'il soit à la bonne place.

heapify sur [4, 5, 3] — le 4 en haut viole la règle :

       4          L'enfant gauche 5 est plus grand → échange
      / \
     5   3

       5          Le 5 est maintenant en haut → règle respectée ✓
      / \
     4   3

Code​

public static void heapSort(int[] arr) {
    int n = arr.length;

    // Phase 1 : construire le tas
    // On part du milieu — les éléments après n/2 n'ont pas d'enfants, déjà valides.
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Phase 2 : extraire le plus grand, le verrouiller à la fin, réparer
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;          // arr[i] est maintenant à sa place finale

        heapify(arr, i, 0);     // on répare uniquement la zone [0..i-1]
    }
}

private static void heapify(int[] arr, int n, int i) {
    while (true) {
        int largest = i;
        int left  = 2 * i + 1;
        int right = 2 * i + 2;

        if (left  < n && arr[left]  > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            i = largest;        // on descend vérifier plus bas
        } else {
            break;              // le parent est déjà le plus grand → stop
        }
    }
}

Exemple pas à pas avec [4, 10, 3, 5, 1]​

Phase 1 — Construction du tas​

Tableau initial :  [4, 10, 3, 5, 1]

         4
       /   \
     10     3
    /  \
   5    1

On commence à i = n/2 - 1 = 1 et on remonte.

heapify i=1 (valeur 10) : enfants 5 et 1 — 10 est déjà le plus grand, rien à faire.

heapify i=0 (valeur 4) : enfant gauche 10 > 4 → échange. On descend : enfants 5 et 1, tous < 10 → stop.

Après Phase 1 : [10, 5, 3, 4, 1]

         10
       /    \
      5      3
    /   \
   4     1

Phase 2 — Extractions​

TourActionTableau (gras = zone triée verrouillée)
i=4Échange 10 ↔ 1, heapify taille 4[5, 4, 3, 1, 10]
i=3Échange 5 ↔ 1, heapify taille 3[4, 1, 3, 5, 10]
i=2Échange 4 ↔ 3, heapify taille 2[3, 1, 4, 5, 10]
i=1Échange 3 ↔ 1[1, 3, 4, 5, 10] ✓

Complexité​

TempsToujours O(n log n) — même dans le pire cas
MémoireO(1) — tri en place, aucune copie du tableau

Youtube​

https://www.youtube.com/watch?v=2DmK_H7IdTo